package pl.poznan.put.cs.to.tsp.heuristics;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import pl.poznan.put.cs.to.tsp.common.IResultHolder;
import pl.poznan.put.cs.to.tsp.common.Vertexes;
import pl.poznan.put.cs.to.tsp.listeners.TSPListener;

public class ExpandingHeuristic implements IResultHolder {
	private LinkedList<Integer> listA;
	private LinkedList<Integer> listB;
	private int lengthA;
	private int lengthB;
	private Vertexes vertexes;
	private TSPListener tspListener;
	private Random random;
	private int minIndexInA = -1;
	private int minIndexInB = -1;

	/**
	 * Previous-next array ( a[i][0] is previous index, a[i][1] is next index,
	 * if -1 vertex is not used yet). In the end of the algorithm this array is
	 * transformed to 2 LinkedLists.
	 */
	private int[][] prevNextArray;

	public ExpandingHeuristic(Vertexes vertexes, TSPListener tspListener) {
		this.vertexes = vertexes;
		this.random = new Random();
		this.tspListener = tspListener;

		this.prevNextArray = new int[this.vertexes.getNumberOfNodes()][2];
		for (int i = 0; i < this.vertexes.getNumberOfNodes(); i++) {
			for (int j = 0; j < 2; j++) {
				this.prevNextArray[i][j] = -1;
			}
		}

		// this.generateResult();
		this.createResult();
		//this.transformResult();
	}

	private void createResult() {
		int count = this.vertexes.getNumberOfNodes();
	}

	private void generateResult() {
		int count = this.vertexes.getNumberOfNodes();

		List<Integer> available = new ArrayList<Integer>();
		for (int i = 0; i < count; i++) {
			available.add(i);
		}

		int res1 = -1;
		int res2 = -1;

		int first = this.random.nextInt(count);
		int rand = this.random.nextInt(count - 1);
		int second = -1;
		if (rand >= first) {
			second = rand + 1;
		} else {
			second = rand;
		}

		double distance = Double.MIN_VALUE;
		double minDistance = this.vertexes.getMaxDistance() * 0.5;

		int actual1 = first;
		int actual2 = second;
		distance = this.vertexes.getDistanceBetween(first, second);
		while (distance < minDistance) {
			a: for (int i = 0; i < count; i++) {
				actual1 = (actual1 + i) % count;
				for (int j = 0; j < count; j++) {
					actual2 = (actual2 + j) % count;
					distance = this.vertexes.getDistanceBetween(actual1,
							actual2);
					if (distance >= minDistance) {
						break a;
					}
				}
			}
		}
		res1 = actual1;
		res2 = actual2;

		available.remove(Integer.valueOf(res1));
		available.remove(Integer.valueOf(res2));

		this.prevNextArray[res1][0] = res1;
		this.prevNextArray[res1][1] = res1;
		this.minIndexInA = res1;
		this.lengthA = 0;

		this.prevNextArray[res2][0] = res2;
		this.prevNextArray[res2][1] = res2;
		this.minIndexInB = res2;
		this.lengthB = 0;
		/*
		 * while (!available.isEmpty()) { int actualIndex =
		 * this.random.nextInt(available.size()); int vActual =
		 * available.remove(actualIndex);
		 * 
		 * int bestA = this.findBestPrevInCycle(this.minIndexInA, vActual); int
		 * bestB = this.findBestPrevInCycle(this.minIndexInB, vActual);
		 * 
		 * if (cA < cB) { // wciskamy do A
		 * 
		 * } else { // wciskamy do B
		 * 
		 * boolean toA = changeA < changeB;
		 * 
		 * if (toA) { this.insert(vActual, bestA); this.lengthA += changeA; }
		 * else { this.insert(vActual, bestB); this.lengthB += changeB; } }
		 * System.out.println("heuristic end.");
		 */
	}

	private void insert(int v, int prev) {
		int succ = this.prevNextArray[prev][1];
		this.prevNextArray[prev][1] = v;
		this.prevNextArray[v][0] = prev;
		this.prevNextArray[v][1] = succ;
		this.prevNextArray[succ][0] = v;
	}

	private int findBestPrevInCycle(int start, int v) {
		int prev = start;
		int res = -1;
		int change = Integer.MAX_VALUE;
		do {
			int c = this.calculateChange(prev, v);
			if (c < change) {
				change = c;
				res = prev;
			}
			prev = this.prevNextArray[prev][1];
		} while (prev != start);
		return res;
	}

	private int calculateChange(int prev, int v) {
		int next = this.prevNextArray[prev][1];
		int c = this.vertexes.getDistanceBetween(prev, v)
				+ this.vertexes.getDistanceBetween(next, v)
				- this.vertexes.getDistanceBetween(prev, next);
		return c;
	}

	@Override
	public int getLengthA() {
		return this.lengthA;
	}

	@Override
	public int getLengthB() {
		return this.lengthB;
	}

	@Override
	public LinkedList<Integer> getListA() {
		return this.listA;
	}

	@Override
	public LinkedList<Integer> getListB() {
		return this.listB;
	}

	@Override
	public Vertexes getVertexes() {
		return this.vertexes;
	}

	@Override
	public int compareTo(IResultHolder o) {
		int local = this.getLengthA() + this.getLengthB();
		int other = o.getLengthA() + o.getLengthB();
		return local - other;
	}

}